public class QuickSort {
        public static int[] quickSort (int[] nums, int low, int high) {

            if (low < high) {
                int index = partition(nums,low,high);
                quickSort(nums,low,index-1);
                quickSort(nums,index+1,high);
            }

            return nums;
        }
        public static int partition (int[] nums, int low, int high) {

            int pivot = nums[low];
            while (low < high) {
                //移动hight指针
                while (low < high && nums[high] >= pivot) {
                    high--;
                }
                //填坑
                if (low < high) nums[low] = nums[high];
                while (low < high && nums[low] <= pivot) {
                    low++;
                }
                //填坑
                if (low < high) nums[high] = nums[low];
            }
            //基准数放到合适的位置
            nums[low] = pivot;
            return low;
        }

        public static void main(String[] args) {
            int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
            int [] newNums = quickSort(nums, 0, nums.length-1);
            for (int x : newNums) {
                System.out.println(x);
            }
        }
    }

